package leetcode.sort;

import java.util.Arrays;

/**
 * 插入排序
 * @author 榆关
 **/
public class InsertSort {
    /**
     * 插入排序的思想，就是从第二个数开始，插入到前面的序列中，保证前面的序列都是顺序的
     */

    public static void main(String[] args) {
        try{
            int[] nums = {3,0,4,1,5,6,2,8,9,7};
            solution(nums);
            System.out.println(Arrays.toString(nums));
        }catch (Exception e){
            e.printStackTrace();
        }
    }

    public static void solution(int[] nums){
        for(int i=1;i<nums.length;i++){
            int temp = nums[i];
            for(int j=i-1;j>=0;j--){
                if(temp<nums[j]){
                    nums[j+1] = nums[j];
                    nums[j] = temp;
                }
            }
        }
    }
    /**
     * 1.当元素的初始序列为正序时，仅外循环要进行n-1趟排序且每一趟只进行一次比较，没有进入if语句不存在元素之间的交换(移动)。此时比较次数(Cmin)和移动次数(Mmin)达到                  最小值。

     Cmin = n-1    Mmin = 0;

     此时时间复杂度为O(n)。

     2.当元素的初始序列为反序时，每趟排序中待插入的元素都要和[0,i-1]中的i个元素进行比较且要将这i个元素后移(arr[j+1] = arr[j])，i个元素后移移动次数当然也就为i                    了，再加上temp = arr[i]与arr[j+1] = temp的两次移动，每趟移动的次数为i+2,此时比较次数(Cmin)和移动次数(Mmin)达到最小值。

     Cmax = 1+2+...+(n-1) = n*(n-1)/2 = O(n2)

     Mmax = (1+2)+(2+2)+...+(n-1+2) = (n-1)*(n+4)/2 = O(n2)  (i取值范围1~n-1)

     此时时间复杂度为O(n2)。

     3.在直接插入排序中只使用了i,j,temp这3个辅助元素，与问题规模无关，所以空间复杂度为O(1).

     4.在整个排序结束后，即使有相同元素它们的相对位置也没有发生变化，

     如：5,3,2,3排序过程如下

     A--3,5,2,3

     B--2,3,5,3

     C--2,3,3,5

     排序结束后两个元素3的相对位置没有发生改变，所以直接插入排序是一种稳定排序。
     */
}
